A high speed circuit for Huffman decoding capable of decoding data at the rate of one pixel per clock cycle, including an additional set of gate arrays for decoding Huffman codes corresponding to a pixel having no leading zeros.
In image handling systems the amount of data per page is quite large. For example, at 300 pixels per inch, a page may have as many as 8 million pixels. Therefore, before storage or transmission, the data is typically compressed. However, if the compression and decompression algorithms are slow, the amount of time required to handle this large amount of data would tie up the system. It is therefore imperative that such a system has a clock frequency as high as possible, and that the algorithms execute at the rate of one pixel per clock cycle.
Huffman coding is a compression technique that assigns the smallest code words to the most common numbers. Thus, to use a numerical example, the code word for a common number like 64 would have a shorter code word than a relatively less common number like 59. However, since there is no specific number of bits per word, the exact starting place of each Huffman encoded word can not be known until the previous one has been decoded, which makes the effective use of a pipelined circuit more difficult.
In image data handling systems it is common for the system to use a predictor prior to compression, which increases the number of zero's between non-zero pixels in the data stream. This is an advantage since data with longer strings of zero's tends to compress better. After that, JPEG (Joint Photographic Expert Group) compression, which is an industry standard, is frequently used. In this system the output of the predictor is converted into a first number defining the run length of leading zeros, a second number denoting the size of the following non-zero pixel, and a set of bits having the actual non-zero pixel data.
To use a numerical example, let us assume that the first four pixels in a data stream after the predictor have values of 0, 0, 0 and -12. (In this system 12 is 1100 and -12 is the one's complement, 0011). The first step is to convert this set of numbers into a new set of three numbers specifying the number of leading zero's (3), the number of bits in the numerical value of the pixel (4) and the numerical value itself (0011). The first two numbers are given a Huffman code (111111110111) and the actual pixel value (0011) is added on to the end. The final compressed value is (1111111101110011).